package com.dyz.otherAlgorithm;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: daiyizheng
 * @date: 2021/7/1 23:38
 * @description:
 */
public class Knapsack {

    public static void main(String[] args) {
        Article[] articles = new Article[]{
                new Article(35, 10),
                new Article(30,40),
                new Article(60, 30),
                new Article(50, 50),
                new Article(40, 35),
                new Article(10, 40),
                new Article(25, 30)
        };
        //排序价值从大到小
        select("价值主导",articles, (Article a1, Article a2)->{
            return a2.value - a1.value;
        });
        //排序重量从小到大
        select("重量主导", articles,(Article a1, Article a2)->{
            return a1.weight - a2.weight;
        });

        select("价值密度主导", articles,(Article a1, Article a2)->{
            return Double.compare(a2.ValueDensity ,a1.ValueDensity);
        });

    }


    static void select(String title, Article[] articles,Comparator<Article> cm){
        Arrays.sort(articles, cm);
        int capacity = 150, weight=0, value=0;
        List<Article> selectedArticle = new LinkedList<>();

        for(int i=0; i<articles.length && weight<capacity; i++){
            int newWeight = weight + articles[i].weight;
            if(newWeight<=capacity){
                weight = newWeight;
                value += articles[i].value;
                selectedArticle.add(articles[i]);
            }
        }
        System.out.println(title);
        System.out.println("总价值: "+value);
        for (Article a:  selectedArticle) {
            System.out.println(a);
        }
    }
}


class Article{
    public int weight;
    public int value;
    public Double ValueDensity;

    public Article(int weight, int value) {
        this.weight = weight;
        this.value = value;
        ValueDensity = value*1.0 /weight;
    }

    @Override
    public String toString() {
        return "Article{" +
                "weight=" + weight +
                ", value=" + value +
                ", ValueDensity=" + ValueDensity +
                '}';
    }
}
